﻿//
// Created by PC on 2022/11/16.
// 希尔排序
//

#include <vector>
#include "arrUtil.h"
using namespace std;

void shell(vector<int> &v)
{
//    printVector(v);
    int len = v.size();
    int gap = len/2;
    while (gap>0)
    {
        for (int i = 0; i+gap < len; i+=gap)
        {
            int cur = v[i+gap];
            int j = i;
            while(v[j]>cur and j>=0)
            {
                v[j+gap]=v[j];
                j-=gap;
            }
            v[j+gap]=cur;
        }
        gap/=2;
    }
}

int main()
{
    vector<int> ve;
    randVector(ve,15);
    printVector(ve);
    shell(ve);
    printf("%d",checkSortVector(ve));
//    printVector(ve);
    return 0;
}
